#ifndef __DFS__
#define __DFS__


#include "meta_search.hpp"
#include <stack>
namespace graph_search{
    // struct 
    // {
    //     int row;
    //     int col;
    //     Node(int _row,int _col):row(_row),col(_col){}
    // };
    
    class DFS:public search{
        public:
            DFS(int _rows,int _cols):rows(_rows),cols(_cols){}
            int find(const std::vector<std::vector<int>>& matrix,Position start,Position end){
                std::stack<Position> stack_v;

                std::vector<std::vector<bool>> visited(rows,std::vector<bool>(cols,false));

                stack_v.push(start);
                visited[start.x][start.y] =true;
                while(!stack_v.empty()){
                    Position current = stack_v.top();
                    stack_v.pop();
                    for(int i=0;i<4;i++){
                        int upRow = current.x - 1;
                        int upCol = current.y;
                        if(isValidNode(current.x+dx[i],current.y+dy[i]) && !visited[current.x+dx[i]][current.y+dy[i]]){
                            stack_v.push({current.x+dx[i],current.y+dy[i]});
                            visited[current.x+dx[i]][current.y+dy[i]] = true;
                        }
                    }
                }
            }
            bool isValidNode(int row,int col){
                return row>=0 && row<rows && col >= 0 && col<cols;
            }
        private:
            int rows;
            int cols;
    };
}

#endif